YoungGyu Blog

부분집합 문제

February 18, 2022

타겟넘버 문제

이해

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 바꾸지않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 사용할 수 있는 숫자가 담긴 배열 numbers,타겟 넘버 target이 매개변수로 주어진다.

계획

  • 재귀 함수는 재귀가 멈추는 조건을 구해야 한다. numbers의 길이가 depth랑 같으면 종료된다.
  • 하나는 -1 하나는 +1 해주는 재귀 함수 두 개를 생성해 준다.
  • 재귀가 호출될 때마다 depth를 +1증가 시켜주고, 깊이가 5와 같고 연산의 합이 target 이면 개수를 +1 시켜준다
  • 마지막에 count를 리턴한다.
const subest = n => {
  const arr = Array(n).fill(0)
  const check = [...arr]
  const result = []
  const dfs = (n, depth) => {
    const arr = []
    if (depth === n) {
      for (let i = 0; i < n; i++) {
        if (check[i] === 1) {
          arr.push(i + 1)
        }
      }
      result.push(arr)
      return
    }
    check[depth] = 1
    dfs(n, depth + 1, check)
    check[depth] = 0
    dfs(n, depth + 1, check)
  }
  dfs(n, 0)
  result.pop()
  return result
}

test('subset', () => {
  expect(subest(3)).toEqual([[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3]])
})

아쉬운점

간단한 dfs문제라 테스트 하나로 끝난 것 같다.

Lee YoungGyu